home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / network / search.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  8KB  |  297 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)search.c    5.2 (Berkeley) 4/8/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include "btree.h"
  44.  
  45. /*
  46.  *  _BT_FIRST -- Find the first item in the tree that matches the supplied
  47.  *         key.
  48.  *
  49.  *    This routine supports deletion.  When the user supplies a key to
  50.  *    be deleted, we find the first one, and iteratively delete all the
  51.  *    matching ones that follow it.
  52.  *
  53.  *    Parameters:
  54.  *        t -- btree in which to find first occurrence
  55.  *        key -- key to find
  56.  *
  57.  *    Returns:
  58.  *        The BTITEM for the matching item.  If there's no match,
  59.  *        this may point to the first item > than the supplied key,
  60.  *        or off the end of the page.
  61.  *
  62.  *    Warnings:
  63.  *        The BTITEM returned is in static space and will be overwritten
  64.  *        by the next search of any kind in any btree.
  65.  */
  66.  
  67. BTITEM *
  68. _bt_first(t, key)
  69.     BTREE_P t;
  70.     DBT *key;
  71. {
  72.     BTHEADER *h;
  73.     BTITEM *item;
  74.     index_t next;
  75.     int r;
  76.  
  77.     /* find any matching item */
  78.     item = _bt_search(t, key);
  79.     h = t->bt_curpage;
  80.     next = NEXTINDEX(h);
  81.  
  82.     /* if we're off the end of the page, search failed and we're done */
  83.     if (item->bti_index >= next)
  84.         return (item);
  85.  
  86.     /* as long as we have an exact match, walk backwards */
  87.     while ((r = _bt_cmp(t, key->data, item->bti_index)) == 0) {
  88.  
  89.         /* at start of page? */
  90.         if (item->bti_index == 0) {
  91.  
  92.             /* if no prev page, we're done */
  93.             if (h->h_prevpg == P_NONE)
  94.                 return (item);
  95.  
  96.             /* walk backward, skipping empty pages */
  97.             do {
  98.                 if (_bt_getpage(t, h->h_prevpg) == RET_ERROR)
  99.                     return ((BTITEM *) NULL);
  100.                 h = t->bt_curpage;
  101.             } while (NEXTINDEX(h) == 0 && h->h_prevpg != P_NONE);
  102.  
  103.             if (NEXTINDEX(h) != 0)
  104.                 item->bti_index = NEXTINDEX(h) - 1;
  105.             else
  106.                 item->bti_index = 0;
  107.  
  108.             item->bti_pgno = h->h_pgno;
  109.         } else {
  110.             item->bti_index--;
  111.         }
  112.     }
  113.  
  114.     /* if we went too far backwards, step forward one entry */
  115.     if (r > 0) {
  116.         if (++(item->bti_index) >= NEXTINDEX(h)
  117.             && h->h_nextpg != P_NONE) {
  118.  
  119.             /* walk forward, skipping empty pages */
  120.             do {
  121.                 if (_bt_getpage(t, h->h_nextpg) == RET_ERROR)
  122.                     return ((BTITEM *) NULL);
  123.                 h = t->bt_curpage;
  124.             } while (h->h_nextpg != P_NONE && NEXTINDEX(h) == 0);
  125.  
  126.             item->bti_index = 0;
  127.             item->bti_pgno = h->h_pgno;
  128.         }
  129.     }
  130.  
  131.     /* got it */
  132.     return (item);
  133. }
  134.  
  135. /*
  136.  *  _BT_SEARCH, _BT_SEARCHR -- Search for a particular key in the tree.
  137.  *
  138.  *    Parameters:
  139.  *        t -- btree in which to search
  140.  *        key -- key to find
  141.  *
  142.  *    Returns:
  143.  *        BTITEM for matching item, if any, or the BTITEM for the
  144.  *        location of the key, if it were in the tree.
  145.  *
  146.  *    Warnings:
  147.  *        The BTITEM returned is in static memory, and will be
  148.  *        overwritten by the next search of any kind in any tree.
  149.  */
  150.  
  151. BTITEM *
  152. _bt_search(t, key)
  153.     BTREE_P t;
  154.     DBT *key;
  155. {
  156.     /* we want to start all of our searches at the root */
  157.     if (_bt_getpage(t, (pgno_t) P_ROOT) == RET_ERROR)
  158.         return ((BTITEM *) NULL);
  159.  
  160.     return (_bt_searchr(t, key));
  161. }
  162.  
  163. BTITEM *
  164. _bt_searchr(t, key)
  165.     BTREE_P t;
  166.     DBT *key;
  167. {
  168.     BTHEADER *h = t->bt_curpage;
  169.     index_t index;
  170.     IDATUM *id;
  171.     DATUM *d;
  172.     static BTITEM item;
  173.  
  174.     /* do a binary search on the current page */
  175.     index = _bt_binsrch(t, key->data);
  176.  
  177.     /*
  178.      *  At this point, the binary search terminated because the endpoints
  179.      *  got too close together, or we have a match.  Figure out which
  180.      *  case applies and decide what to do based on the page type.
  181.      */
  182.     if (h->h_flags & F_LEAF) {
  183.         item.bti_pgno = h->h_pgno;
  184.         item.bti_index = index;
  185.         if (index < NEXTINDEX(h))
  186.             d = (DATUM *) GETDATUM(h,index);
  187.         else
  188.             d = (DATUM *) NULL;
  189.  
  190.         item.bti_datum = d;
  191.         return(&item);
  192.     } else {
  193.         id = (IDATUM *) GETDATUM(h, index);
  194.         if (_bt_push(t, h->h_pgno) == RET_ERROR)
  195.             return ((BTITEM *) NULL);
  196.         if (_bt_getpage(t, id->i_pgno) == RET_ERROR)
  197.             return ((BTITEM *) NULL);
  198.         return (_bt_searchr(t, key));
  199.     }
  200. }
  201.  
  202. /*
  203.  *  _BT_BINSRCH -- Do a binary search for a given key on the current page.
  204.  *
  205.  *    Searches on internal pages are handled slightly differently from
  206.  *    searches on leaf pages.  This is because internal page searches
  207.  *    find the largest item <= key in the tree, and leaf searches find
  208.  *    the smallest item >= key.  This guarantees that leaf page searches
  209.  *    leave us pointing at the item's correct position, and internal
  210.  *    searches descend the tree correctly.
  211.  *
  212.  *    Parameters:
  213.  *        t -- tree to search
  214.  *        key -- key we're looking for
  215.  *
  216.  *    Returns:
  217.  *        Index of the line pointer array entry for the (closest)
  218.  *        match to key on the current page, with "closest" as defined
  219.  *        above.
  220.  */
  221.  
  222. index_t
  223. _bt_binsrch(t, key)
  224.     BTREE_P t;
  225.     char *key;
  226. {
  227.     index_t lbound, ubound, cur;
  228.     BTHEADER *h = t->bt_curpage;
  229.     int match = 0;
  230.     int r;
  231.  
  232.     lbound = 0;
  233.     ubound = NEXTINDEX(h);
  234.     if (ubound > 0)
  235.         --ubound;
  236.  
  237.     /* do a binary search on the current page */
  238.     while ((ubound - lbound) > 1) {
  239.         cur = lbound + ((ubound - lbound) / 2);
  240.         r = _bt_cmp(t, key, cur);
  241.  
  242.         if (r > 0)
  243.             lbound = cur + 1;
  244.         else if (r < 0)
  245.             ubound = cur;
  246.         else {
  247.             match++;
  248.             break;
  249.         }
  250.     }
  251.  
  252.     /*
  253.      *  At this point, the binary search terminated because the endpoints
  254.      *  got too close together, or we have a match.  Figure out which
  255.      *  case applies, decide what to do based on the page type (leaf or
  256.      *  internal), and do the right thing.
  257.      */
  258.     if (match) {
  259.         return (cur);
  260.     } else if (ubound != lbound) {
  261.         if (h->h_flags & F_LEAF) {
  262.             r = _bt_cmp(t, key, lbound);
  263.             if (r <= 0) {
  264.                 return (lbound);
  265.             }
  266.         } else {
  267.             r = _bt_cmp(t, key, ubound);
  268.  
  269.             /* for internal nodes, move as far left as possible */
  270.             if (r < 0) {
  271.                 r = _bt_cmp(t, key, lbound);
  272.                 if (r < 0 && lbound > 0)
  273.                     --lbound;
  274.                 return (lbound);
  275.             } else {
  276.                 return (ubound);
  277.             }
  278.         }
  279.     }
  280.  
  281.     if (h->h_flags & F_LEAF) {
  282.         if (ubound < NEXTINDEX(h)) {
  283.             r = _bt_cmp(t, key, ubound);
  284.             if (r > 0)
  285.                 ubound++;
  286.         }
  287.     } else {
  288.         /* for internal pages, move as far left as possible */
  289.         if (ubound == NEXTINDEX(h))
  290.             ubound--;
  291.  
  292.         while (_bt_cmp(t, key, ubound) < 0)
  293.             ubound--;
  294.     }
  295.     return (ubound);
  296. }
  297.